package com.fyt.algorithm.Leecode.day8_5;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class FindAnagrams {
    /**
     * 我的遍历加排序的解决方案
     * @param s
     * @param p
     * @return
     */
    public static List<Integer> findAnagrams(String s, String p) {
        char[] arrayP = p.toCharArray();
        Arrays.sort(arrayP);
        p=new String(arrayP);

        int lengthP=p.length();
List res=new ArrayList();

        for (int i = 0; i < s.length()-lengthP+1; i++) {
          String stringSub=s.substring(i,lengthP+i);
          char[] arraySub=stringSub.toCharArray();
          Arrays.sort(arraySub);
          stringSub=new String(arraySub);
          if(stringSub.equals(p)){
              res.add(i);
          }
        }



        return res;
    }


    /**
     * 滑动窗口
     * 使用数组来存储字符串 p 和滑动窗口中每种字母的数量(类似计数排序的处理方式)
     * @param p
     * @param s
     */
    public static List<Integer> findAnagrams2(String s, String p){
        int sLen=s.length(), pLen=p.length();
        //特殊情况排除
        if(sLen<pLen){
            return new ArrayList<>();

        }
        //初始化滑动窗口,创建迭代起点
        int[]sCount=new int[26];//将要存储的是字母
        int[]pCount=new int[26];
        List res=new ArrayList();
        for (int i = 0; i <pLen ; i++) {
            pCount[p.charAt(i)-'a']++;
            sCount[s.charAt(i)-'a']++;
}
        if(Arrays.equals(sCount,pCount)){
            res.add(0);
        }

        //正式开始滑动
        for (int i = 1; i <sLen-pLen+1 ; i++) {
            sCount[s.charAt(i-1)-'a']--;
            sCount[s.charAt(i+pLen-1)-'a']++;
            if(Arrays.equals(pCount, sCount)){
                res.add(i);
            }
        }


        return res;
    }


    public static void main(String[] args) {
       // String s = "abab", p = "ab";
        String s = "cbaebabacd", p = "abc";
        System.out.println(findAnagrams2(s,p));
    }
}
